#include "stdio.h"

#define MAXVEX 20
#define MAXEDGE 20
#define INFINITY 65535

typedef struct {
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numNodes, numEdges;
}MGraph;

// 用于存储最短路径下标的数组
typedef int Patharc[MAXVEX];
// 用于存储到各点最短路径的权值和
typedef int ShortPathTable[MAXVEX];

// P[v]的值为前驱顶点v的下标，D[v]表示v0到v的最短路径权值和
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D) {
    int v,w,k,min;
    // final数组的作用类似最小生成树中的lowcost，当值为0时表示顶点还没加入最短路径，当值为1时表明顶点已经加入最短路径
    int final[MAXVEX];
    // 初始化数据
    for(v=0;v<G.numNodes;v++) {
        // 默认都未加入最短路径
        final[v] = 0;
        // 从顶点v0开始，将与v0有连线的顶点权值存入数组
        (*D)[v] = G.arc[v0][v];
        // 默认全为-1，即目前还没有路径
        (*P)[v] = -1;
    }
    // 从v0开始，故v0到v0自身权值为0
    (*D)[v0] = 0;
    // v0默认加入最短路径
    final[v0] = 1;
    // 开始求最短路径，每次求得v0到某个顶点v的最短路径
    for (v = 1; v < G.numNodes; v++) {
        min = INFINITY;
        // 寻找离v0顶点最近的顶点
        for(w = 0; w < G.numNodes; w++) {
            // 未加入最短路径且其离v0最近（即权值最小），就交换并记录
            if(!final[w] && (*D)[w] < min) {
                k = w;
                min = (*D)[w];
            }
        }
        // 找到后加入最短路径
        final[k] = 1;
        // 从找到的顶点再次出发，继续寻找权值和最小的顶点
        for (w = 0; w < G.numNodes; w++) {
            // 未加入最短路径且从上面已加入最短路径的顶点再出发，找权值和最小的顶点
            if(!final[w] && min + G.arc[k][w] < (*D)[w]) {
                // 若有更小的，更新数组里的权值
                (*D)[w] = min + G.arc[k][w];
                // 记录顶点vw的前驱顶点的下标k
                (*P)[w] = k;
            }
        }
    }
}